package first.niuke.simple;

/**
 * @ClassName NC106
 * @description:
 * @author: 荣燊
 * @create: 2021-06-14 15:57
 **/
public class NC106 {
    // 三个数的最大乘积
    // 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，
    // 要求时间复杂度：O(n)，空间复杂度：O(1)。
    public static void main(String[] args) {
        int[] a = {3472,7789,7955,-7098,-9281,6101,5051,7778,3090,7423,-7151,5652,
                1595,-8094,677,-8324,8347,-2482,9313,-9338,-3157,8559,6945,3618,
                3087,121,-8468,3225,1356, 6939,2799,-7231,-6309,-5453,633,-8689,
                -4776,2714,-2743,-1409,5918,-3333,1803, 8330, -2206,-6117,-4486,-7903,-4375,
                -3739,2897,8056,-5864,-522,7451,-4541,-2813,5790,
                -532,-6517,925};

//        Arrays.first.sort(a);
//        for (int b : a) {
//            System.out.print("\\");
//            System.out.print(b);
//        }

        System.out.println(solve(a));
    }

    /**
     * 分情况考虑吧，
     */
    public static long solve (int[] A) {
        // write code here
//        Arrays.first.sort(A); // 时间复杂度，不能用
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for(int num : A){
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }

            if(num < min1){
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max((long)max1*max2*max3, (long)max1*min1*min2);
    }

}
